"""
遗传算法实现字符串生成与匹配

问题描述：
    从随机字符开始，通过遗传算法逐步生成目标字符串"Genetic Algorithm Demo"。
    这是一个模式匹配问题，展示了遗传算法在搜索和优化中的应用。

算法原理：
    将字符串生成视为进化过程：
    - 编码方式：ASCII码表示字符，每个基因对应一个字符
    - 适应度函数：与目标字符串匹配的字符数量比例
    - 选择方法：基于适应度的轮盘赌选择
    - 交叉操作：两点交叉，交换部分字符序列
    - 变异操作：随机字符变异，以小概率替换为新字符
    - 终止条件：找到完全匹配的字符串或达到最大迭代次数

应用场景：
    字符串匹配问题是遗传算法的经典演示案例，类似技术可应用于：
    - 密码破解与模式识别
    - 自然语言处理中的文本生成
    - 生物序列比对与分析
    - 进化计算教学演示

可视化：
    实时显示每代最优个体，匹配字符显示为绿色，不匹配字符显示为红色，
    直观展示进化过程中字符串逐渐接近目标的过程。

作者：斯黄
日期：2025年3月4日
"""

# 遗传算法生成目标字符串 "Genetic Algorithm Demo"
import numpy as np
import matplotlib.pyplot as plt

TARGET = "Genetic Algorithm Demo"
DNA_SIZE = len(TARGET)       # 字符串长度
POP_SIZE = 300               # 种群规模
CROSS_RATE = 0.8             # 交叉概率
MUT_RATE = 0.01              # 变异概率
N_GENERATIONS = 1000         # 迭代次数
ASCII_RANGE = [32, 126]      # 可打印ASCII码范围

# 适应度计算（匹配字符数）
def get_fitness(pop):
    match = (pop == np.array([ord(c) for c in TARGET])).sum(axis=1)
    return match / DNA_SIZE  # 返回匹配比例

# 创建新个体
def create_individual():
    return np.random.randint(*ASCII_RANGE, size=DNA_SIZE)

# 两点交叉
def crossover(parent, pop):
    if np.random.rand() < CROSS_RATE:
        i_ = np.random.randint(0, POP_SIZE, size=1)
        cross_points = np.random.randint(0, 2, DNA_SIZE).astype(bool)
        parent[cross_points] = pop[i_, cross_points]
    return parent

# 随机位变异
def mutate(child):
    for point in range(DNA_SIZE):
        if np.random.rand() < MUT_RATE:
            child[point] = np.random.randint(*ASCII_RANGE)
    return child

# 初始化种群
pop = np.array([create_individual() for _ in range(POP_SIZE)])

# 进化过程
plt.ion()
fig, ax = plt.subplots(figsize=(8, 2))
text = ax.text(0.5, 0.5, '', fontsize=20, ha='center', va='center')
ax.axis('off')

for generation in range(N_GENERATIONS):
    fitness = get_fitness(pop)
    best = pop[np.argmax(fitness)]
    current_str = ''.join([chr(c) for c in best])
    colors = ['green' if a==b else 'red' for a,b in zip(current_str, TARGET)]
    text.set_text('\n'.join([
        f'Generation: {generation}',
        ''.join([f'<span style="color:{c}">{s}</span>' for s,c in zip(current_str, colors)])
    ]))
    plt.pause(0.05)

    # 选择
    idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True, p=fitness/fitness.sum())
    pop = pop[idx]
    
    # 交叉变异
    for i in range(POP_SIZE):
        parent = pop[i]
        child = crossover(parent, pop)
        child = mutate(child)
        pop[i] = child

    # 终止条件
    if ''.join([chr(c) for c in best]) == TARGET:
        break

plt.ioff()
plt.show() 